Tags: loop invariants, selection sort
Suppose you are sorting an array using selection sort. At the current iteration of selection sort, the array being sorted looks like this:
[0, 1, 2, 2, 3, 4, 2, 10, 13, 4]
Which of the following are possible options for how many times the outer for loop has run? Select all that apply.
1, 2, 3, and 4. Remember the selection sort loop invariants: after the \(\alpha\)th iteration, the first \(\alpha\) numbers are \(\leq\) the remaining numbers, and the first \(\alpha\) numbers are in sorted order.
To answer this question, we can ask, for each \(\alpha\), are the loop invariants true? If yes, then it is possible that \(\alpha\) iterations have been made; if not, then it is not possible.
It is true for \(\alpha=1\), since the first number is \(\leq\) the remaining numbers, and the first 1 numbers are in sorted order. Same for \(\alpha = 2, 3, \) and \(4\). However, it is not true at \(\alpha = 5\). One of the loop invariants is true (the first five numbers are in sorted order), but the other is not: the first 5 numbers are not all \(\leq\) the remaining numbers. In particular, the fifth number (3) is not \(\leq\) the 7th number (2). Therefore, this could not possibly be the result after 5 iterations.